package com.wlr.study.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 路径总和 II
 *
 * @author lrwang
 * @version 1.0
 * @date 2022/4/7 19:44
 */
public class LeetCode113 {
    List<List<Integer>> result=new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        if (root == null) {
            return result;
        }
        List<Integer> list = new LinkedList<>();
        isTrue(root, targetSum, list);
        return result;
    }

    public void isTrue(TreeNode cur, int count, List<Integer> list) {
        list.add(cur.val);
        if (cur.left == null && cur.right == null) {
            if (count - cur.val == 0) {
                result.add(new ArrayList<>(list));
            }
            return;
        }
        if (cur.left != null) {
            isTrue(cur.left, count - cur.val, list);
            list.remove(list.size() - 1);
        }
        if (cur.right != null) {
            isTrue(cur.right, count - cur.val, list);
            list.remove(list.size() - 1);
        }
    }

}
